package binary_search;

/**
 *  LCR 173.点名（一题多解）
 */
public class Demo20250404 {
    public int takeAttendance(int[] records) {
        // 解法1: 位运算 ^
        // 异或数组中的所有数字
        // 0,1,2,3,5
        int num = 0;
        for (int x : records) {
            num ^= x;
        }
        // 用num异或从0到records.left的所有数字
        // 0^1^2^3^5^0^1^2^3^4^5
        // = 4
        for (int i = 0; i <= records.length; i++) {
            num ^= i;
        }
        return num;
        // [0] return 1  没错!


        // // 解法2：求和公式
        // int n = records.length;
        // int sum = (0 + n) * (n + 1) / 2;
        // for (int i = 0; i < records.length; i++) {
        //     sum -= records[i];
        // }
        // return sum;


        // // 解法3：直接遍历查找
        // for (int i = 0; i < records.length; i++) {
        //     if (records[i] != i) {
        //         return i;
        //     }
        // }
        // // 处理细节
        // return records.length;


        // // 解法4：哈希表
        // // 创建哈希表
        // boolean[] hash = new boolean[records.length + 1];
        // // 有数字的下标中放入 true
        // for (int nums : records) {
        //     hash[nums] = true;
        // }
        // // 遍历hash表，哪个位置不是true就返回哪个下标
        // for (int i = 0; i < records.length; i++) {
        //     if (!hash[i]) {
        //         return i;
        //     }
        // }
        // return records.length;


        // // 解法5：二分查找
        // int left = 0, right = records.length - 1;
        // while (left < right) {
        //     int mid = left + (right - left) / 2;
        //     if (records[mid] == mid) {
        //         left = mid + 1;
        //     } else {
        //         right = mid;
        //     }
        // }
        // // 如果最后left和right重合的位置值和下标相同，代表数组严格递增，则返回left+1
        // return records[left] == left ? left + 1 : left;
    }
}
